/** \file    SplitLarge.cpp
  * \brief   Splits segments larger than a threshold and writes result in a segmentation image.
  * \date    2001 - 2003
  * \author  Fedor Chelnokov
  * \version $Header: /home/cscom1r4/cvsroot/cs/segm/src/SplitLarge.cpp,v 1.2 2005/04/04 04:10:16 cscom1r4 Exp $
  */

#include <algorithm>

#include "imglib/bitmap.h"
#include "imglib/image.h"
#include "math/random.h"
#include "vec2d/vec2d.h"
#include "xtd/kDimTree.h"

#include "cinline.h"

#include "segm/Segmentation.h"

using vec2d::Vec2d;

//starts of smaller subsegments
struct SeedPoint: public Vec2d {
	small_byte_color color;
	int sumx,sumy;	///< summed position of subsegment points
	int pixelCount;	///< total pixels in subsegment
};

static inline void reset_sum(SeedPoint &s)
	{ s.sumx = s.sumy = s.pixelCount = 0; }

typedef xtd::kDimTree<SeedPoint, Vec2d, double, 2>	SeedTree;
typedef std::vector<SeedPoint>						SeedArr;
typedef std::vector<int>							IntArr;

///replaces SeedPoints in array with new ones formed from operator() input
class NewSeeds
{
public:
	NewSeeds(SeedArr &seedArr) : 
		_seedArr(seedArr), _n(0) {}
	~NewSeeds()
		{ assert (_n == _seedArr.size()); }
	void operator()(const SeedPoint &c)
		{ SeedPoint &s = _seedArr[_n++];
		  s.x = double(c.sumx) / c.pixelCount;
		  s.y = double(c.sumy) / c.pixelCount; }

private:
	SeedArr &_seedArr;
	size_t	 _n;
};

///splits one segment
static void split1(
	const Segment & g,
	const Segmentation & gS,
	const img::bitmap & gMask,
	byte_image & dest,
	int diam,
	IntArr & seedColors,
	int splitReclusteringCycles
)
{
	SeedArr seedArr;

	img::bitmap::const_iterator i;
	for (i = gMask.begin(); i != gMask.end(); ++i) {
		if (!*i)
			continue;
		size_t x = i.x() + g.boundingBox.x1;
		size_t y = i.y() + g.boundingBox.y1;

		SeedArr::reverse_iterator r;
		for (r = seedArr.rbegin(); r != seedArr.rend(); ++r)
			if (fabs(r->x - x)<diam && fabs(r->y - y)<diam) 
				break;
		if (r != seedArr.rend())
			continue;

		//create new seed point
		SeedPoint s;
		s.x = x;
		s.y = y;
		int i = 50;
		do {
			s.color = small_byte_color( 
				limit(g.color.b+g_draw(i)-i/2, 0, 255),
				limit(g.color.g+g_draw(i)-i/2, 0, 255),
				limit(g.color.r+g_draw(i)-i/2, 0, 255)
			);
			++i;
		} while (color2int(s.color) == 0 || 
				 gS.pSegmentByColor(color2int(s.color))!=0 ||
				 std::binary_search(seedColors.begin(), seedColors.end(), color2int(s.color)));

		seedArr.push_back(s);

		seedColors.push_back(color2int(s.color));
		std::inplace_merge(seedColors.begin(), seedColors.end()-1, seedColors.end());
	}

	for (int c = 0; c <= splitReclusteringCycles; ++c) {
		bool lastCycle = c == splitReclusteringCycles;

		std::for_each(seedArr.begin(), seedArr.end(), reset_sum);

		SeedTree seedTree;
		seedTree.Create(&*seedArr.begin(), seedArr.size());

		for (i = gMask.begin(); i != gMask.end(); ++i) {
			if (!*i)
				continue;
			size_t x = i.x() + g.boundingBox.x1;
			size_t y = i.y() + g.boundingBox.y1;
			SeedPoint *s = const_cast<SeedPoint*>(seedTree.FindNearestPoint(Vec2d(x,y), DBL_MAX));
			assert(s);

			if (lastCycle) {
				dest(x,y) = s->color;
			} else {
				++s->pixelCount;
				s->sumx += x;
				s->sumy += y;
			}
		}

		if (!lastCycle) {
			seedTree.m_pRoot->enumSubTree(NewSeeds(seedArr));
		}
	}
}

///draws segment on image
static void drawSeg(const Segment &g, const img::bitmap &gMask, byte_image & dest)
{
	img::bitmap::const_iterator i;
	for (i = gMask.begin(); i != gMask.end(); ++i) {
		if (!*i)
			continue;
		size_t x = i.x() + g.boundingBox.x1;
		size_t y = i.y() + g.boundingBox.y1;

		dest(x,y) = g.color;
	}
}

/** splited segmentstion is written in dest-picture, because of hardness of neighbourhood correction */
void Segmentation::splitLarge(int largePcount, int targetPcount, byte_image & dest,
	int splitReclusteringCycles) const
{
	int w = width();
	int h = height();
	dest.resize(w, h);
	img::fill(dest, byte_color());
	int diam = round(sqrt(float(targetPcount)));

	IntArr seedColors; //ordered array of colors designated to just formed seed points

	const_cast<Segmentation*>(this)->positions();
	size_t gi;
	img::bitmap gMask;
	for (gi = 0; gi != count(); ++gi) {
		segmentMask(gi, gMask);
		const Segment &g = segmentByIndex(gi);
		if (g.pixelCount >= largePcount)
			split1(g, *this, gMask, dest, diam, seedColors, splitReclusteringCycles);
		else
			drawSeg(g, gMask, dest);
	}
}
